public class Test {

    public static void getNext(String sub,int[] next){
        next[0] = -1;
        next[1] = 0;
        int k = 0;
        int i = 2;

        for(;i<sub.length();){
            if(k == -1 ||sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k+1;
                k++;
                i++;
            }else{
                k = next[k];
            }
        }
    }
    /**
     * @param str 主字符串
     * @param sub 子字符串
     * @param pos 主字符串起始查找位置
     * @return 返回与字串相匹配的主串起始位置
     */
    public static int KMP(String str, String sub, int pos) {
        if(str == null || sub ==null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) return -1;
        if (pos < 0 || pos >= lenStr) return -1;

        int i = pos;//遍历主串
        int j = 0;//遍历字串
        int[] next = new int[lenSub];
        getNext(sub,next);

        while(i<lenStr && j<lenSub){
            if(j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(j >= lenSub){
            return i - j;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(KMP("cbabababadbababccd", "ababab", 0));
    }
}
